There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1: nums1 = [1, 3] nums2 = [2]

The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5



In [60]:

    
import pdb
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        先排查两个数组，
        而后一个个排查数组，
        具体思想就是每次记录两个值，
        median一定在比较时最小的那个值，
        tmp是上一次的median
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        # nums1 list length
        nums1_len = len(nums1)
        nums2_len = len(nums2)
        
        i, j, k = 0, 0, -1
        odd = True if (nums1_len + nums2_len) % 2 == 1  else False
        median_index = int((nums1_len + nums2_len) / 2)
        tmp = -1
        median = 0
        while i < nums1_len and j < nums2_len:
            tmp = median
            if nums1[i] < nums2[j]:
                median = nums1[i]
                i += 1
            else:
                median = nums2[j]
                j+= 1
            k += 1
            
            if k == median_index and odd:
                return median
            elif k == median_index and not odd:
                return (median+tmp)/ 2.0
        while i < nums1_len:
            tmp = median
            median = nums1[i]
            i+=1
            k += 1
            if k == median_index and odd:
                return median
            elif k == median_index and not odd:
                return (median+tmp)/ 2
        while j < nums2_len:
            tmp = median
            median = nums2[j]
            j += 1
            k += 1
            if k == median_index and odd:
                return median
            elif k == median_index and not odd:
                return (median+tmp)/ 2



In [61]:

    
nums1 = [1, 3]
nums2 = [2]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 2









    Out[61]:





2



In [45]:

    
nums1 = [1, 2]
nums2 = [3, 4]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 2.5









    Out[45]:





2.5



In [46]:

    
nums1 = [1, 2, 3, 4]
nums2 = [5, 6]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 3.5









    Out[46]:





3.5



In [47]:

    
nums1 = [1, 2]
nums2 = [3, 4, 5, 6]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 3.5









    Out[47]:





3.5



In [48]:

    
nums1 = [1, 2, 3, 4, 4]
nums2 = [3, 4, 5, 6]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 4









    Out[48]:





4



In [49]:

    
nums1 = [1, 3]
nums2 = [2]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 2









    Out[49]:





2



In [50]:

    
nums1 = []
nums2 = [1]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 1









    Out[50]:





1



In [51]:

    
nums1 = []
nums2 = [2, 3 ]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 2.5









    Out[51]:





2.5



In [52]:

    
nums1 = []
nums2 = [2, 3, 4 ]
Solution().findMedianSortedArrays(nums1, nums2) # answer is 3









    Out[52]:





3



In [53]:

    
nums1 = [2, 3, 4 ]
nums2 = []
Solution().findMedianSortedArrays(nums1, nums2) # answer is 3









    Out[53]:





3



In [58]:

    
nums1 = [3, 4]
nums2 = []
Solution().findMedianSortedArrays(nums1, nums2) # answer is 3.5









    Out[58]:





3.5



In [59]:

    
nums1 = [2]
nums2 = []
Solution().findMedianSortedArrays(nums1, nums2) # answer is 2









    Out[59]:





2

leetcode一定要看清楚，我们用的是python还是python3，哭死了



In [ ]: